/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025-02-16
 * Time: 16:11
 */
public class BinarySearchTree {

    public static class Node{
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }
    //根节点是整颗树的根节点，所以定义在内部类之外
    private Node root = null;
    //插入
    public void insert(int key){
        if (root == null) {
            root = new Node(key);
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if (cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if (cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                System.out.println("存在相同元素,无法插入");
                return;
            }
        }
        //此时的parent节点，要么是叶子节点，要么左右子树至少有一边为空
        Node node = new Node(key);
        if (parent.val < key){
            parent.right = node;
        }
        if (parent.val > key){
            parent.left = node;
        }
    }
    //删除
    public void del(int key){
        if (root == null){
            System.out.println("为空,无法删除");
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if (cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if (cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                //删除节点的具体逻辑
                scapegoat(parent,cur);
                return;
            }
        }
        System.out.println("没找到你要删除的元素");
    }
    //寻找替罪羊节点
    private void scapegoat(Node parent,Node cur){
        if (cur.left == null){
            //左树为空且cur是根节点
            if (cur == root){
                root = root.right;
            //左树为空且cur是parent的左子节点
            }else if (cur == parent.left){
                parent.left = cur.right;
            //左树为空且cur是parent的右子节点
            }else {
                parent.right = cur.right;
            }
        }else if (cur.right == null){
            //右树为空且cur是根节点
            if (cur == root){
                root = root.left;
            //右树为空且cur是parent的右子节点
            }else if (cur == parent.right){
                parent.right = cur.left;
            //右树为空且cur是parent的左子节点
            }else {
                parent.left = cur.left;
            }
        //左右子树都不为空
        }else {
            //找到右子树的最左边的子节点
            Node tempParent = cur;
            Node temp = cur.right;
            while (temp.left != null){
                tempParent = temp;
                temp = temp.left;
            }
            //把右子树 的 左子树 的 最左边的节点覆盖掉cur节点
            cur.val = temp.val;
            if (temp == tempParent.left){
                tempParent.left = temp.right;
            }else {
                tempParent.right = temp.right;
            }
        }
    }
    //查找
    public int find(int key){
        if (root == null){
            System.out.println("为空,无法查找");
            return -1;
        }
        Node cur = root;
        while (cur != null){
            if (cur.val > key){
                cur = cur.left;
            }else if (cur.val < key){
                cur = cur.right;
            }else {
                return cur.val;
            }
        }
        System.out.println("没有这个元素");
        return -1;
    }
}
